package com.daycode;

/**
 * @author 孔德成
 * @slogan 致敬大师，致敬未来的你
 * @date 2021/9/29 8:05 下午
 * @desc
 */
public class ArrayCode {
    /**
     * 704. 二分查找
     * 双指针
     * https://leetcode-cn.com/problems/binary-search/
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }
        return -1;
    }

    /**
     * 27. 移除元素
     * 双指针
     * https://leetcode-cn.com/problems/remove-element/
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        // 快指针，使用快指针遍历每个元素
        int fast;
        // 慢指针
        int slow = 0;
        for (fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                // 快指针指向的元素不等于要删除的值，则慢指针移动
                slow++;
            }
        }
        return slow;
    }

    /**
     * 977. 有序数组的平方
     * 双指针
     * https://leetcode-cn.com/problems/squares-of-a-sorted-array/
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int i = 0, j = nums.length - 1, k = j;
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                res[k] = nums[i] * nums[i];
                i++;
            } else {
                res[k] = nums[j] * nums[j];
                j--;
            }
            k--;
        }
        return res;
    }

    /**
     * 209. 长度最小的子数组
     * 滑动窗口法
     * https://leetcode-cn.com/problems/minimum-size-subarray-sum/
     *
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        // 滑动窗口法
        int result = Integer.MAX_VALUE;
        int sum = 0;
        // 窗口起始位置
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            // j = 窗口结束位置
            sum += nums[right];
            while (sum >= target) {
                // 计算子数组的长度
                int sub = (right - left) + 1;
                // 返回更短的子数组长度
                result = Math.min(result, sub);
                // 根据窗口大小不断移动窗口起始位置
                sum -= nums[left++];
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
